class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
    }
}
/**
 * https://leetcode-cn.com/problems/palindrome-linked-list/
 * 是不是回文链表
 * @param head 
 */
const isPalindrome = (head: ListNode | null): boolean => {
    // head为空 不是回文链表
    if (head === null) return false;

    // 只有一个元素, 是回文链表
    if (head.next === null) return true;

    // 1. 寻找中间元素
    const getMid = (head: ListNode) => {
        let slow = head,
            fast: ListNode | null = head;

        // 遍历, 直到fast为空
        while (fast && fast.next !== null) {
            slow = slow.next!;
            fast = fast.next.next;
        }

        // fast为空时, slow就是中间
        return slow;
    }

    const mid = getMid(head);

    // 2. 把中间节点进行翻转
    const reverse = (head: ListNode | null) => {
        let newHead: ListNode | null = null;

        while (head !== null) {
            // 保存头节点的下一个
            const n = head.next;

            head.next = newHead;
            newHead = head;
            head = n
        }

        return newHead;
    }
    // 新的头结点
    let newHead = reverse(mid),
        tail = newHead,
        h: ListNode | null = head;
    // 前后进行比较
    while (h !== null && tail !== null) {
        // 值不相等, 直接返回
        if (h.val !== tail.val) return false
        h = h.next;
        tail = tail.next;
    }

    // 恢复链表
    // reverse(newHead);

    return true
};

const isPalindrome2 = (head: ListNode | null): boolean => {
    // head为空 不是回文链表
    if (head === null) return true;

    // 只有一个元素, 是回文链表
    if (head.next === null) return true;

    // 1. 遍历链表, 放入数组中
    const arr: number[] = []
    let l: ListNode | null = head;
    while (l !== null) {
        arr.push(l.val);
        l = l.next;
    }

    // 2. 两个指针
    let h = 0,
        t = arr.length - 1;

    while (h < t) {
        // 只要有一个项不同, 直接返回false
        if (arr[h] !== arr[t]) return false

        // 头部往后, 尾部往前
        h++;
        t--;
    }

    return true
};

const head = new ListNode(1);
head.next = new ListNode(2)
head.next.next = new ListNode(3)
head.next.next.next = new ListNode(2)
head.next.next.next.next = new ListNode(1)

isPalindrome(head);

export {}